1. Field of the Invention
The invention relates to the field of circuit design and, more particularly, to floorplanning techniques for Programmable Logic Devices (PLD's).
2. Description of the Related Art
Floorplanning is the first step in generating a placement for a Very Large Scale Integrated (VLSI) circuit design. The task of floorplanning is to generate an overlap-free placement of a set of modules subject to optimization criteria such as net length and path delays. The generated floorplan guides the subsequent placement step in the PLD design process.
Floorplanning operates on a contracted netlist that contains the modules and the consolidated connectivity between the various associated components forming the modules. A net exists between a set of modules if one or more nets exist in the original netlist that connect components which are part of these modules. Every net in the contracted netlist can be assigned a weight, which corresponds to the number of nets in the original netlist which that net represents.
In illustration, FIG. 1 is a schematic diagram illustrating a netlist 100 corresponding to a PLD such as a Field Programmable Gate Array (FPGA). The device has 10 components C1, . . . , C10. Related components have been grouped into three modules, M1, M2, and M3. The contracted netlist is shown in bold. As shown, there are two nets connecting components in modules M1 and M2 and one net connecting components in modules M1 and M3. Consequently, the netlist representation shown in FIG. 1 contains a net of weight 2 between modules M1 and M2 and a net of weight 1 between modules M1 and M3.
Modules can be represented during the floorplanning process as sequence pairs. Generally, a sequence pair is a one-dimensional, computational model of two-dimensional modules and the associated components of each module. A sequence pair SPi can include two strings, where each is a perturbation of all k modules of the design. Two exemplary sequence pairs of the netlist in FIG. 1 can be SP0=((M3, M2, M1), (M2, M1, M3)) or SP1=((M1, M1, M3), (M3, M1, M2)). There is a 1:1 relationship between a sequence pair and a floorplan with well defined methods to generate a floorplan from a sequence pair and vice versa.
An iterative optimization technique can be applied to the PLD using the sequence pair representation. The optimization technique can begin with a random solution, such as a random sequence pair, and start swapping modules between one of the two sequences in the sequence pair. The optimization process can continue until one or more of a plurality of design criteria have been achieved.
As shown in FIG. 1, conventional floorplanning techniques utilize modules having a single predefined shape. Contrary to Application Specific Integrated Circuits (ASIC's), floorplanning of FPGA devices requires determining non-overlapping locations for these fixed-shape modules within the fixed area constraints of the FPGA device. Thus, modules M1, M2, and M3 have been located within a cell 105 of a FPGA device having a fixed area.
Although modern FPGA designs can include a variety of different components of varying sizes including, but not limited to, registers, block random access memory (RAM), multipliers, processors, and the like, each component must be placed within a fixed-size module and located on the FPGA device. This is the case despite the heterogeneity of the components and component sizes. Accordingly, although area requirements of a module can vary with the type of components located within that module, designers are limited to using a fixed-shape module despite the heterogeneity of the components located therein.
What is needed is an improved methodology for performing floorplanning with respect to PLD designs.